package sivan.letcode;

import org.apache.ibatis.javassist.compiler.ast.Pair;
import org.junit.Test;
import sivan.domain.User;

import java.util.*;

//https://leetcode-cn.com/problems/two-sum/
public class LetCode1 {

    /**
     * 两数之和等于target
     *
     * @param nums
     * @param target
     * @return
     */
    public int[] twoSum(int[] nums, int target) {
        for (int i = 0; i < nums.length - 1; i++) {
            if (nums[i] > target) {
                continue;
            }
            for (int j = i + 1; j < nums.length; j++) {
                if (nums[j] > target) {
                    continue;
                }
                if (nums[i] + nums[j] == target) {
                    return new int[]{i, j};
                }
            }
        }
        throw new IllegalArgumentException("No two sum solution");
    }

    /**
     * 两数之和等于target
     *
     * @param nums
     * @param target
     * @return
     */
    public int[] twoSum2(int[] nums, int target) {
        Map<Integer, Integer> map = new HashMap<>();
        for (int i = 0; i < nums.length; i++) {
            if (map.containsKey(target - nums[i])) {
                return new int[]{map.get(target - nums[i]), i};
            }
            map.put(nums[i], i);
        }
        throw new IllegalArgumentException("No two sum solution");
    }


    public static int lengthOfLongestSubstring(String s) {
        int n = s.length();
        if (n == 0) {    //如果为空字符串，直接返回0
            return 0;
        }
        //因为本题中字符串只含有英文字母，符号和数字，所以可以使用数组来代替哈希表，提高效率。
        int[] num = new int[128];
        int res = 0;
        //left: 左指针    right: 右指针
        int left = 0, right = 0;
        //将字符串转换为一个char数组,写起来方便
        char[] cs = s.toCharArray();

        while (right < n) {
            //每次循环都将右侧指针向前移动一位，并将右侧指针所指向的字符的数量增加1
            //(byte) cs[right]表示将字符cs[right]转换为其所对应的ASCII码，在0~127之间，
            //恰好可以使用byte表示
            num[(byte) cs[right]]++;
            //如果此时右侧指针所对应的字符的数量超过1，表示已经有了重复字符，将左指针右移
            while (num[(byte) cs[right]] > 1) {
                num[(byte) cs[left++]]--;
            }
            //更新结果，取之前的结果与当前窗口长度的最大值
            res = Math.max(res, right - left + 1);
            //右指针右移
            right++;
        }
        return res;
    }

    public static void main(String[] args) {
        int a = maxGy(63, 144);
        for (int i = 0; i < 100; i++) {
            if (isPrime(i)) {
                System.out.print(i + ",");
            }
        }
        System.out.println(a);
    }

    /**
     * 计算中位数
     *
     * @param nums1
     * @param nums2
     * @return
     */
    public double findMedianSortedArrays(int[] nums1, int[] nums2) {
        int l1 = nums1.length;
        int l2 = nums2.length;
        int total = l1 + l2;
        int[] newNums = new int[total];

        int index = 0;
        if (l1 > 0) {
            for (int value : nums1) {
                newNums[index] = value;
                index++;
            }
        }
        if (l2 > 0) {
            for (int value : nums2) {
                newNums[index] = value;
                index++;
            }
        }

        Arrays.sort(newNums);
        if (total % 2 == 1) {
            return newNums[total / 2];
        } else {
            int a = newNums[total / 2];
            int b = newNums[total / 2 - 1];
            double sum = a + b;
            return sum / 2;
        }
    }

    /**
     * 最大回文数
     *
     * @param s
     * @return
     */
    public String longestPalindrome(String s) {
        int length = s.length();
        if (length < 2) {
            return s;
        }
        char[] arr = s.toCharArray();
        int count = 0;
        int maxLeft = 0, maxRight = 1;
        for (int i = length - 1; i > 0; i--) {
            int left = longestPalindrome(arr, i, i);
            int right = longestPalindrome(arr, i, i + 1);
            int l = Math.max(left, right);
            count = Math.max(count, l);
            if (count == l) {
                maxLeft = i - (l - 1) / 2;
                maxRight = i + l / 2;
            }
        }
        return s.substring(maxLeft, maxRight + 1);
    }

    private int longestPalindrome(char[] arr, int left, int right) {
        while (left >= 0 && right < arr.length && arr[left] == arr[right]) {
            left--;
            right++;
        }
        return right - left - 1;
    }

    public static String convert(String s, int numRows) {
        if (numRows == 1) return s;

        StringBuilder ret = new StringBuilder();
        int n = s.length();
        int cycleLen = 2 * numRows - 2;

        char[] arr = s.toCharArray();
        for (int i = 0; i < numRows; i++) {
            for (int j = 0; j + i < n; j += cycleLen) {
                ret.append(arr[j + i]);
                if (i != 0 && i != numRows - 1 && j + cycleLen - i < n)
                    ret.append(arr[j + cycleLen - i]);
            }
        }
        return ret.toString();
    }


    public static int reverse(int x) {
        String str = String.valueOf(x);

        char[] arr = str.replace("-", "")
                .toCharArray();
        StringBuilder builder = new StringBuilder();
        for (int i = arr.length - 1; i >= 0; i--) {
            builder.append(arr[i]);
        }

        long result = Long.parseLong(builder.toString());
        if (result > Integer.MAX_VALUE) {
            return 0;
        }
        return x >= 0 ? (int) result : -(int) result;
    }


    public int myAtoi(String str) {
        str = str.trim();
        if (str.length() == 0) return 0;
        if (!Character.isDigit(str.charAt(0))
                && str.charAt(0) != '-' && str.charAt(0) != '+')
            return 0;
        long ans = 0L;
        boolean neg = str.charAt(0) == '-';
        int i = !Character.isDigit(str.charAt(0)) ? 1 : 0;
        while (i < str.length() && Character.isDigit(str.charAt(i))) {
            ans = ans * 10 + (str.charAt(i++) - '0');
            if (!neg && ans > Integer.MAX_VALUE) {
                ans = Integer.MAX_VALUE;
                break;
            }
            if (neg && ans > 1L + Integer.MAX_VALUE) {
                ans = 1L + Integer.MAX_VALUE;
                break;
            }
        }
        return neg ? (int) -ans : (int) ans;
    }

    /**
     * 判断是否是回文数
     *
     * @param x
     * @return
     */
    public static boolean isPalindrome(int x) {
        String s = String.valueOf(x);
        char[] arr = s.toCharArray();
        int length = arr.length;
        if (length <= 0) {
            return false;
        }
        for (int i = 0; i < length; i++) {
            if (arr[i] != arr[length - i - 1]) {
                return false;
            }
        }
        return true;
    }

    /**
     * 最大面积
     *
     * @param height
     * @return
     */
    public int maxArea(int[] height) {
        int left = 0;
        int right = height.length - 1;
        int ans = 0;
        while (left < right) {
            int a = Math.min(height[left], height[right]);
            ans = Math.max(ans, a * (right - left));
            if (height[left] <= height[right]) {
                left++;
            } else {
                right--;
            }
        }
        return ans;
    }

    /**
     * 罗马数字
     *
     * @param num
     * @return
     */
    public String intToRoman(int num) {
        int[] values = {1000, 900, 500, 400, 100, 90, 50, 40, 10, 9, 5, 4, 1};
        String[] symbols = {"M", "CM", "D", "CD", "C", "XC", "L", "XL", "X", "IX", "V", "IV", "I"};
        StringBuilder builder = new StringBuilder();
        for (int i = 0; i < values.length; i++) {
            int value = values[i];
            String symbol = symbols[i];
            while (num >= value) {
                num -= value;
                builder.append(symbol);
            }
        }
        return builder.toString();
    }

    /**
     * 罗马数字转阿拉伯数字
     *
     * @param s
     * @return
     */
    public static int romanToInt(String s) {
        s = s.replace("IV", "f");
        s = s.replace("IX", "e");
        s = s.replace("XL", "d");
        s = s.replace("XC", "c");
        s = s.replace("CD", "b");
        s = s.replace("CM", "a");

        Map<Character, Integer> map = new HashMap<>();
        map.put('M', 1000);
        map.put('a', 900);
        map.put('D', 500);
        map.put('b', 400);
        map.put('C', 100);
        map.put('c', 90);
        map.put('L', 50);
        map.put('d', 40);
        map.put('X', 10);
        map.put('e', 9);
        map.put('V', 5);
        map.put('f', 4);
        map.put('I', 1);
        int result = 0;
        for (int i = 0; i < s.length(); i++) {
            result += map.get(s.charAt(i));
        }
        return result;
    }

    /**
     * 最长公共前缀
     *
     * @param strs
     * @return
     */
    public static String longestCommonPrefix(String[] strs) {
        if (strs.length == 0) {
            return "";
        }

        if (strs.length == 1) {
            return strs[0];
        }

        String temp = strs[0];
        for (int i = 1; i < strs.length; i++) {
            if (!strs[i].startsWith(temp)) {
                i--;
                temp = temp.substring(0, temp.length() - 1);
            }
        }
        return temp;
    }

    /**
     * 三数之和
     *
     * @param nums
     * @return
     */
    public static List<List<Integer>> threeSum(int[] nums) {
        int n = nums.length;
        Arrays.sort(nums);
        List<List<Integer>> ans = new ArrayList<>();
        if (n < 3 || nums[0] > 0 || nums[n - 1] < 0) {
            return ans;
        } else if (nums[0] == 0 && nums[n - 1] == 0) {
            List<Integer> threeNums = Arrays.asList(0, 0, 0);
            ans.add(threeNums);
            return ans;
        }

        for (int aIndex = 0; aIndex < n; ++aIndex) {
            if (aIndex > 0 && nums[aIndex] == nums[aIndex - 1]) {
                continue;
            }

            if (nums[aIndex] > 0) {
                break;
            }

            int cIndex = n - 1;
            int target = -nums[aIndex];

            for (int bIndex = aIndex + 1; bIndex < n; ++bIndex) {
                if (bIndex > aIndex + 1 && nums[bIndex] == nums[bIndex - 1]) {
                    continue;
                }
                while (bIndex < cIndex && nums[bIndex] + nums[cIndex] > target) {
                    --cIndex;
                }

                if (bIndex == cIndex) {
                    break;
                }

                if (nums[bIndex] + nums[cIndex] == target) {
                    List<Integer> threeNums = Arrays.asList(nums[aIndex], nums[bIndex], nums[cIndex]);
                    ans.add(threeNums);
                }
            }
        }
        return ans;
    }

    public int threeSumClosest(int[] nums, int target) {
        Arrays.sort(nums);
        int n = nums.length;
        int best = 10000000;

        for (int i = 0; i < n; ++i) {
            if (i > 0 && nums[i] == nums[i - 1]) {
                continue;
            }

            int j = i + 1, k = n - 1;
            while (j < k) {
                int sum = nums[i] + nums[j] + nums[k];
                if (sum == target) {
                    return target;
                }
                if (Math.abs(sum - target) < Math.abs(best - target)) {
                    best = sum;
                }
                if (sum > target) {
                    int k0 = k - 1;
                    while (j < k0 && nums[k0] == nums[k]) {
                        --k0;
                    }
                    k = k0;
                } else {
                    int j0 = j + 1;
                    while (j0 < k && nums[j0] == nums[j]) {
                        ++j0;
                    }
                    j = j0;
                }
            }
        }
        return best;
    }

    /**
     * 电话号码的字母组合
     *
     * @param digits
     * @return
     */
    public static List<String> letterCombinations(String digits) {
        int l = digits.length();
        if (l == 0) {
            return new ArrayList<>();
        }

        Map<Character, List<Character>> map = new HashMap<>();
        map.put('2', Arrays.asList('a', 'b', 'c'));
        map.put('3', Arrays.asList('d', 'e', 'f'));
        map.put('4', Arrays.asList('g', 'h', 'i'));
        map.put('5', Arrays.asList('j', 'k', 'l'));
        map.put('6', Arrays.asList('m', 'n', 'o'));
        map.put('7', Arrays.asList('p', 'q', 'r', 's'));
        map.put('8', Arrays.asList('t', 'u', 'v'));
        map.put('9', Arrays.asList('w', 'x', 'y', 'z'));

        List<String> result = new ArrayList<>();
        List<String> resp = new ArrayList<>();
        char[] arr = digits.toCharArray();
        for (char a : arr) {
            List<Character> c = map.get(a);
            if (result.size() == 0) {
                for (Character s : c) {
                    resp.add(String.valueOf(s));
                }
            } else {
                resp.clear();
                for (String temp : result) {
                    for (Character s : c) {
                        resp.add(temp + s);
                    }
                }
            }

            if (l == 1) {
                return resp;
            }

            if (resp.size() > 0) {
                result.clear();
                result.addAll(resp);
            }
        }
        return resp;
    }

    class ListNode {
        int val;
        ListNode next;

        ListNode() {
        }

        ListNode(int val) {
            this.val = val;
        }

        ListNode(int val, ListNode next) {
            this.val = val;
            this.next = next;
        }
    }

    public ListNode removeNthFromEnd(ListNode head, int n) {
        ListNode newNode = new ListNode(0, head);
        int length = 0;
        while (head != null) {
            head = head.next;
            length++;
        }

        ListNode cur = newNode;
        for (int i = 1; i < length - n + 1; i++) {
            cur = cur.next;
        }

        cur.next = cur.next.next;
        return newNode.next;
    }

    /**
     * 给定一个只包括 '('，')'，'{'，'}'，'['，']' 的字符串 s
     * 判断字符串是否有效。
     *
     * @param s
     * @return
     */
    public boolean isValid(String s) {
        int n = s.length();
        if (n % 2 == 1 || n == 0) {
            return false;
        }
        Map<Character, Character> map = new HashMap<Character, Character>() {{
            put(')', '(');
            put(']', '[');
            put('}', '{');
        }};

        char[] arr = s.toCharArray();
        Deque<Character> stack = new LinkedList<>();
        for (char c : arr) {
            if (map.containsKey(c)) {
                if (stack.isEmpty() || stack.peek() != map.get(c)) {
                    return false;
                }
                stack.pop();
            } else {
                stack.push(c);
            }
        }
        return stack.isEmpty();
    }


    public ListNode mergeTwoLists(ListNode l1, ListNode l2) {
        if (l1 == null && l2 == null) {
            return null;
        }
        List<Integer> arr = new ArrayList<>();
        while (l1 != null) {
            arr.add(l1.val);
            l1 = l1.next;
        }

        while (l2 != null) {
            arr.add(l2.val);
            l2 = l2.next;
        }

        int length = arr.size();
        arr.sort(Integer::compareTo);
        ListNode newNode = new ListNode(arr.get(length - 1), null);
        if (length >= 2) {
            for (int i = length - 2; i >= 0; i--) {
                newNode = new ListNode(arr.get(i), newNode);
            }
        }

        return newNode;
    }

    /**
     * 数字 n 代表生成括号的对数，请你设计一个函数，
     * 用于能够生成所有可能的并且 有效的 括号组合。
     */
    List<String> res = new ArrayList<>();

    public List<String> generateParenthesis(int n) {
        if (n <= 0) {
            return res;
        }
        getParenthesis("", n, n);
        return res;
    }

    private void getParenthesis(String str, int left, int right) {
        if (left == 0 && right == 0) {
            res.add(str);
            return;
        }

        if (left == right) {
            getParenthesis(str + "(", left - 1, right);
        } else {
            if (left > 0) {
                getParenthesis(str + "(", left - 1, right);
            }
            getParenthesis(str + ")", left, right - 1);
        }
    }

    /**
     * 最大公约数
     *
     * @param m
     * @param n
     * @return
     */
    public static int maxGy(int m, int n) {
        if (m % n == 0) return n;
        return maxGy(n, m % n);
    }

    public static boolean isPrime(int n) {
        int max = (int) Math.sqrt(n);
        for (int i = 2; i <= max; i++) {
            if (n % i == 0) {
                return false;
            }
        }
        return true;
    }

    @Test
    public void testArrayDeque() {

        Deque<String> deque = new ArrayDeque<>();
        deque.addFirst("aaaa");
        deque.addFirst("bbb");
        deque.pop();
        System.out.println(deque.pop());
        Map<String, String> map = new HashMap<>();
        map.put("1","1");
        map.put("2","1");
        map.put("3","1");
        map.put("4","1");
        Set<Map.Entry<String, String>> d = map.entrySet();
        System.out.println(d);
    }

}
